package heap.simple;

import java.util.PriorityQueue;

/**
 * 最小的k个数
 * 示例 1：
 *
 * 输入：arr = [3,2,1], k = 2
 * 输出：[1,2] 或者 [2,1]
 * 示例 2：
 *
 * 输入：arr = [0,1,2,1], k = 1
 * 输出：[0]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof
 */
public class MinimumNumberOfK_40 {
    public int[] getLeastNumbers(int[] arr, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        for (int i : arr) {
            maxHeap.offer(i);
            if (k < maxHeap.size())
                maxHeap.poll();
        }
        int[] list = new int[maxHeap.size()];
        int i = 0;
        while (!maxHeap.isEmpty())
            list[i++] = maxHeap.poll();
        return list;
    }

    public static void main(String[] args) {
        MinimumNumberOfK_40 mn = new MinimumNumberOfK_40();
        for (int leastNumber : mn.getLeastNumbers(new int[]{0, 1, 2, 1}, 1)) {
            System.out.println(leastNumber);
        }
    }
}
